import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/18 16:24
 * @description 埃氏筛法：如果x是质数，那么2x, 3x一定不是质数，从小到大用一个数组标记
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    public int countPrimes(int n) {
        int[] isPrime = new int[n];
        // 1代表是质数
        Arrays.fill(isPrime, 1);
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            if (isPrime[i] == 1) {
                ans += 1;
                if ((long) i * i < n) {
                    // i是质数，那么 i * i，i * (i + 1) i * (i + 2)肯定不是质数，直接筛掉
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return ans;
    }
}
